#include <vector>
#include <deque>
#include <list>
#include <iostream>

using std::cout;
using std::endl;
using std::vector;
using std::deque;
using std::list;

//在写模板时，如果容器定义了这些成员类型时，
//根本就不需要知道具体的容器，他们都有这些成员类型
template <class Container>
void display(const Container & c)
{//形参使用了const关键字，则迭代器也必须要是const的
    typename Container::const_iterator it = c.begin();
    while(it != c.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}
//总结:
//list适合在任意位置添加/删除元素
//但是查找元素的速度比较慢
//
//vector和deque查找元素的速度很快，O(1)
//但是不适合在任意位置频繁地添加和删除元素

void test0()
{
    vector<int> numbers {1, 3, 5, 7};
    cout << "numbers's size:" << numbers.size() << endl;
    cout << "numbers's capacity:" << numbers.capacity() << endl;

    display(numbers);

    //在任意位置插入元素
    auto it = numbers.begin();
    //该操作时间复杂度不是O(1)
    numbers.insert(it, 2);//可能会发生扩容操作, 对于vector来说开销比较大
    cout << "添加完元素之后:" << endl;
    cout << "numbers's size:" << numbers.size() << endl;
    cout << "numbers's capacity:" << numbers.capacity() << endl;
    cout << "*it:" << *it << endl;//虽然可以调用，但得到的值是不确定的值
    //当执行完插入操作以后，最好是重新获取迭代器的位置
    it = numbers.begin();
    cout << "*it:" << *it << endl;//ok
    display(numbers);
    numbers.emplace_back(10);
}

void test1()
{
    cout << "\ntest1() deque" << endl;
    deque<int> numbers {1, 3, 5, 7};
    cout << "numbers's size:" << numbers.size() << endl;
    display(numbers);

    //在任意位置插入元素
    auto it = numbers.begin();
    ++it;
    ++it;
    cout << "*it:" << *it << endl;
    //该操作时间复杂度不是O(1)
    ////对于deque来说开销比较大
    //与vector相比，没有空间的回收,空间还在
    //所以还是可以获取到有效数据,但可能不是原有的数据
    //如果还希望得到原来的数据，也需要重新进行迭代器的获取
    numbers.insert(it, 2);
    cout << "添加完元素之后:" << endl;
    cout << "numbers's size:" << numbers.size() << endl;
    cout << "*it:" << *it << endl;
    numbers.insert(it, 5, 10);
    display(numbers);
}

void test2()
{
    cout << "\ntest2() list" << endl;
    list<int> numbers {1, 3, 5, 7};
    cout << "numbers's size:" << numbers.size() << endl;
    display(numbers);

    //在任意位置插入元素
    auto it = numbers.begin();
    //该操作时间复杂度为O(1)
    numbers.insert(it, 2);//对于list来说开销很小
    cout << "添加完元素之后:" << endl;
    cout << "numbers's size:" << numbers.size() << endl;
    cout << "*it:" << *it << endl;
    display(numbers);
}

int main()
{
    test0();
    test1();
    test2();

    return 0;
}

